use std::sync::atomic::{AtomicUsize, Ordering};
#[repr(C)]
struct _AVLTree {}
#[repr(C)]
struct _AVLTreeNode {}
type AVLTree = _AVLTree;
type AVLTreeNode = _AVLTreeNode;
type AVLTreeKey = *mut std::ffi::c_void;
type AVLTreeValue = *mut std::ffi::c_void;
#[derive(Debug, Clone, Copy, PartialEq)]
enum AVLTreeNodeSide {
    AVL_TREE_NODE_LEFT,
    AVL_TREE_NODE_RIGHT,
}
type AVLTreeCompareFunc = fn(AVLTreeValue, AVLTreeValue) -> i32;
static AVL_TREE_NULL: *mut std::ffi::c_void = std::ptr::null_mut();
const NUM_TEST_VALUES: usize = 1000;
type UnitTestFunction = fn();
static NUM_ASSERT: AtomicUsize = AtomicUsize::new(0);
static mut TEST_ARRAY: [i32; NUM_TEST_VALUES] = [0; NUM_TEST_VALUES];
static mut COUNTER: i32 = 0;
static TESTS: &[UnitTestFunction] = &[
    test_avl_tree_new,
    test_avl_tree_free,
    test_avl_tree_child,
    test_avl_tree_insert_lookup,
    test_avl_tree_lookup,
    test_avl_tree_remove,
    test_avl_tree_to_array,
    test_out_of_memory,
];
fn find_subtree_height(node: *mut AVLTreeNode) -> i32 {
    if node.is_null() {
        return 0;
    }
    let left_subtree = unsafe { avl_tree_node_child(node, AVL_TREE_NODE_LEFT) };
    let right_subtree = unsafe { avl_tree_node_child(node, AVL_TREE_NODE_RIGHT) };
    let left_height = find_subtree_height(left_subtree);
    let right_height = find_subtree_height(right_subtree);
    if left_height > right_height {
        left_height + 1
    } else {
        right_height + 1
    }
}
fn validate_subtree(node: *mut AVLTreeNode) -> i32 {
    let mut left_node: *mut _AVLTreeNode;
    let mut right_node: *mut _AVLTreeNode;
    let mut left_height: i32;
    let mut right_height: i32;
    let key: *mut i32;
    if node.is_null() {
        return 0;
    }
    left_node = avl_tree_node_child(node, AVL_TREE_NODE_LEFT);
    right_node = avl_tree_node_child(node, AVL_TREE_NODE_RIGHT);
    if !left_node.is_null() {
        assert_eq!(avl_tree_node_parent(left_node), node);
    }
    if !right_node.is_null() {
        assert_eq!(avl_tree_node_parent(right_node), node);
    }
    left_height = validate_subtree(left_node);
    key = avl_tree_node_key(node) as *mut i32;
    assert!(*key > COUNTER);
    COUNTER = *key;
    right_height = validate_subtree(right_node);
    assert_eq!(avl_tree_subtree_height(left_node), left_height);
    assert_eq!(avl_tree_subtree_height(right_node), right_height);
    assert!((left_height - right_height).abs() < 2);
    if left_height > right_height {
        return left_height + 1;
    } else {
        return right_height + 1;
    }
}
fn validate_tree(tree: &mut AVLTree) {
    let root_node: *mut _AVLTreeNode;
    let height: i32;
    root_node = avl_tree_root_node(tree);
    if !root_node.is_null() {
        height = find_subtree_height(root_node);
        assert_eq!(avl_tree_subtree_height(root_node), height);
    }
    unsafe {
        counter = -1;
    }
    validate_subtree(root_node);
}
fn create_tree() -> Rc<AVLTree> {
    let tree = avl_tree_new(int_compare);
    for i in 0..NUM_TEST_VALUES {
        unsafe {
            test_array[i] = i as i32;
            avl_tree_insert(tree.clone(), &test_array[i], &test_array[i]);
        }
    }
    tree
}
#[test]
fn test_avl_tree_new() {
    unsafe {
        let mut tree: *mut _AVLTree;
        tree = avl_tree_new(int_compare as AVLTreeCompareFunc);
        assert!(!tree.is_null());
        assert!(avl_tree_root_node(tree).is_null());
        assert!(avl_tree_num_entries(tree) == 0);
        avl_tree_free(tree);
        alloc_test_set_limit(0);
        tree = avl_tree_new(int_compare as AVLTreeCompareFunc);
        assert!(tree.is_null());
    }
}
#[test]
fn test_avl_tree_insert_lookup() {
    static mut TREE: Option<Box<_AVLTree>> = None;
    static mut TEST_ARRAY: [i32; NUM_TEST_VALUES as usize] = [0; NUM_TEST_VALUES as usize];
    unsafe {
        TREE = Some(avl_tree_new(int_compare as AVLTreeCompareFunc));
        for i in 0..NUM_TEST_VALUES {
            TEST_ARRAY[i as usize] = i as i32;
            avl_tree_insert(
                TREE.as_mut().unwrap(),
                &TEST_ARRAY[i as usize] as *const i32 as *mut i32,
                &TEST_ARRAY[i as usize] as *const i32 as *mut i32,
            );
            assert!(avl_tree_num_entries(TREE.as_mut().unwrap()) == (i + 1) as usize);
            validate_tree(TREE.as_mut().unwrap());
        }
        assert!(avl_tree_root_node(TREE.as_mut().unwrap()).is_some());
        for i in 0..NUM_TEST_VALUES {
            let node = avl_tree_lookup_node(TREE.as_mut().unwrap(), &i as *const i32 as *mut i32);
            assert!(node.is_some());
            let value = avl_tree_node_key(node.unwrap());
            assert!(*value == i as i32);
            let value = avl_tree_node_value(node.unwrap());
            assert!(*value == i as i32);
        }
        let i = NUM_TEST_VALUES + 100;
        assert!(
            avl_tree_lookup_node(TREE.as_mut().unwrap(), &i as *const i32 as *mut i32).is_none()
        );
        avl_tree_free(TREE.take().unwrap());
    }
}
#[test]
fn test_avl_tree_child() {
    let values = [1, 2, 3];
    let mut tree = unsafe { avl_tree_new(Some(int_compare as AVLTreeCompareFunc)) };
    for i in 0..3 {
        unsafe {
            avl_tree_insert(
                tree,
                &values[i] as *const i32 as *mut i32,
                &values[i] as *const i32 as *mut i32,
            );
        }
    }
    unsafe {
        let root = avl_tree_root_node(tree);
        let p = avl_tree_node_value(root);
        assert!(*p == 2);
        let left = avl_tree_node_child(root, AVL_TREE_NODE_LEFT);
        let p = avl_tree_node_value(left);
        assert!(*p == 1);
        let right = avl_tree_node_child(root, AVL_TREE_NODE_RIGHT);
        let p = avl_tree_node_value(right);
        assert!(*p == 3);
        assert!(avl_tree_node_child(root, 10000).is_null());
        assert!(avl_tree_node_child(root, 2).is_null());
        avl_tree_free(tree);
    }
}
#[test]
fn test_out_of_memory() {
    let mut tree: *mut _AVLTree;
    let mut node: *mut _AVLTreeNode;
    let mut i: i32;
    tree = create_tree();
    alloc_test_set_limit(0);
    for i in 10000..20000 {
        node = avl_tree_insert(tree, &i, &i);
        assert!(node.is_null());
        validate_tree(tree);
    }
    avl_tree_free(tree);
}
#[test]
fn test_avl_tree_free() {
    let mut tree: *mut _AVLTree;
    tree = unsafe { avl_tree_new(Some(int_compare as AVLTreeCompareFunc)) };
    unsafe { avl_tree_free(tree) };
    tree = unsafe { create_tree() };
    unsafe { avl_tree_free(tree) };
}
#[test]
fn test_avl_tree_lookup() {
    let mut tree = create_tree();
    let mut i: i32;
    let num_test_values = NUM_TEST_VALUES as i32;
    for i in 0..num_test_values {
        let value = avl_tree_lookup(tree.as_mut(), &i);
        assert!(value.is_some());
        assert!(*value.unwrap() == i);
    }
    i = -1;
    assert!(avl_tree_lookup(tree.as_mut(), &i).is_none());
    i = NUM_TEST_VALUES + 1;
    assert!(avl_tree_lookup(tree.as_mut(), &i).is_none());
    i = 8724897;
    assert!(avl_tree_lookup(tree.as_mut(), &i).is_none());
    avl_tree_free(tree);
}
#[test]
fn test_avl_tree_remove() {
    let mut tree = create_tree();
    let mut i: i32;
    let value: i32;
    let mut expected_entries: u32;
    i = NUM_TEST_VALUES + 100;
    assert_eq!(avl_tree_remove(&mut tree, &i), 0);
    i = -1;
    assert_eq!(avl_tree_remove(&mut tree, &i), 0);
    expected_entries = NUM_TEST_VALUES;
    for x in 0..10 {
        for y in 0..10 {
            for z in 0..10 {
                let value = z * 100 + (9 - y) * 10 + x;
                assert_ne!(avl_tree_remove(&mut tree, &value), 0);
                validate_tree(&tree);
                expected_entries -= 1;
                assert_eq!(avl_tree_num_entries(&tree), expected_entries);
            }
        }
    }
    assert!(avl_tree_root_node(&tree).is_none());
    avl_tree_free(tree);
}
#[test]
fn test_avl_tree_to_array() {
    let mut tree: *mut _AVLTree;
    let entries = [89, 23, 42, 4, 16, 15, 8, 99, 50, 30];
    let sorted = [4, 8, 15, 16, 23, 30, 42, 50, 89, 99];
    let num_entries = entries.len();
    let mut i: usize;
    let mut array: *mut *mut i32;
    unsafe {
        tree = avl_tree_new(Some(int_compare as AVLTreeCompareFunc));
        for i in 0..num_entries {
            avl_tree_insert(
                tree,
                &entries[i] as *const i32 as *mut libc::c_void,
                std::ptr::null_mut(),
            );
        }
        assert!(avl_tree_num_entries(tree) == num_entries);
        array = avl_tree_to_array(tree) as *mut *mut i32;
        for i in 0..num_entries {
            assert!(*(*array.add(i)) == sorted[i]);
        }
        libc::free(array as *mut libc::c_void);
        alloc_test_set_limit(0);
        array = avl_tree_to_array(tree) as *mut *mut i32;
        assert!(array.is_null());
        validate_tree(tree);
        avl_tree_free(tree);
    }
}
fn main() {
    run_tests(tests);
    println!("num_assert: {}", num_assert);
}
